#include<vector>
#include<cmath>
#include<algorithm>
using std::min;
using std::sqrt;
using std::vector;


class Solution {
public:
    int numSquares(int n) {
        vector<int> nums(n+1, INT_MAX);
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 2; i < nums.size(); i++) {
            for (int k = 1; k <= int(sqrt(i)); k++) {
                nums[i] = min(nums[i], nums[i - k*k]);
            }
            nums[i]++;
        }
        return nums[n];
    }
};